5 10
0 0 300
0 1 400
1 2 250
1 3 350
2 4 180
2 5 220
3 6 450
3 7 320
4 8 280
4 9 380
4
0 120 1
1 180 2
2 220 3
3 250 4
8
0 0 6 120
1 1 3 180
2 2 5 80
3 4 0 220
4 3 6 150
5 5 1 50
6 7 8 200
7 9 2 250